#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include "sy_core.h"

namespace MAP {

	const int DET[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
	CAN map_black_dir[N+1][N+1];
	CAN map_white_dir[N+1][N+1];
};

namespace AI {

	const int K_NUM=2,K_TABL=9,K_REV=0;
	const int IMP_STEP = 11;
	const int V[N+1][N+1]={

		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0,999999, -9999, 999, 995, 995, 999, -9999,999999},
		{0, -9999, -9999,  -9,  -9,  -9,  -9, -9999, -9999},
		{0,   999,    -9,   3,   3,   3,   3,    -9,   999},
		{0,   995,    -9,   3,   0,   0,   3,    -9,   995},
		{0,   995,    -9,   3,   0,   0,   3,    -9,   995},
		{0,   999,    -9,   3,   3,   3,   3,    -9,   999},
		{0, -9999, -9999,  -9,  -9,  -9,  -9, -9999, -9999},
		{0,999999, -9999, 999, 995, 995, 999, -9999,999999}
	};
	const int e3[9] = {1,3,9,27,81,243,729,2187,6561};
	const int fv[9] = {0,18,-18,8,8,8,8,-18,18};
	/*	
		{0,0,0,0,0},
		{0,9999,-999,-999,9999},
		{0, -99,   0,   0, -99},
		{0, -99,   0   ,0, -99},
		{0,9999,-999,-999,9999}*/
	POS* NOW_BORDER;
	int f[MAXS][2];
	bool calced[MAXS][2],termin;
	int MAX_DEP=8;
	int Next_x,Next_y;
};

using namespace MAP;

int AI::dfs_dp(int now,int who) {

	if (calced[now][who]) return f[now][who];
	int tmp[10],S = now,next,score = 0,fact = who ? 1 : 2;
	tmp[0] = tmp[9] = -1;

	f[now][who] = who ? INF : -INF;
	for (int j = 8; j >= 1; j--)
	{
		tmp[j] = S % 3;
		S /= 3;
	}

	bool flag = 0;
	for (int j = 1; j <= 8; j++)
	{
		if (!tmp[j])
		{
			int l,r;
			for (l = j - 1; tmp[l] == who + 1; l--);
			for (r = j + 1; tmp[r] == who + 1; r++);
			if (tmp[l] != fact || l == j - 1) l = 0;
			if (tmp[r] != fact || r == j + 1) r = 0;
			if (l || r)
			{
				flag = 1;
				if (l) for (int t = l + 1; t < j; t++) tmp[t] = fact;
				if (r) for (int t = j + 1; t < r; t++) tmp[t] = fact;
				tmp[j] = fact;
				next = 0;
				for (int t = 8,k = 0; t >= 1; t--,k++) next += e3[k] * tmp[t];
				if (!who)
				{
					if (dfs_dp(next,1) > f[now][0]) f[now][0] = f[next][1];
				}
				else if (dfs_dp(next,0) < f[now][1]) f[now][1] = f[next][0];
				tmp[j] = 0;
				if (l) for (int t = l + 1; t < j; t++) tmp[t] = 3 - fact;
				if (r) for (int t = j + 1; t < r; t++) tmp[t] = 3 - fact;
			}
		}
		else if (tmp[j] == 1) score -= fv[j];
		else score += fv[j];
	}
	if (!flag) f[now][who] = score;
	calced[now][who] = 1;
	return f[now][who];
}

void AI::Initdp() {

	memset(calced,0,sizeof(calced));
	for (int i = 0; i < MAXS; i++)
	{
		dfs_dp(i,0);
		dfs_dp(i,1);
	}
}

void AI::AI_next(int P_MAP,POS *BD,int NOW_BNUM,int NOW_WNUM,int &Fx,int &Fy) {

	NOW_BORDER=BD;
	int T_MAP[N + 1][N + 1],left;
	memmove(T_MAP,MAP,MAP_SIZE);
	if ((left = N * N - NOW_BNUM - NOW_WNUM) <= 18) 
	{
		MAX_DEP = IMP_STEP;
		if (left <= 11) termin = 1; else termin = 0;
	}
	int res = Black_search(T_MAP,NOW_BNUM,NOW_WNUM,1,-INF - 1,INF + 1,0);
	if (res == -INF) 
	{
		int PUT_NUM,rp;
		POS_D PUTPOSS[257];
		Can_drop_black(MAP,PUTPOSS,NOW_BORDER,PUT_NUM);
		rp = rand() % PUT_NUM + 1;
		Fx = PUTPOSS[rp].x;
		Fy = PUTPOSS[rp].y;
		printf("Failed\n");
	}//I'll fail anyway..
	else
	{
		Fx = Next_x; 
		Fy = Next_y;
	}
}

int AI::Get_value(int P_MAP,int B_NUM,int W_NUM,int dep,int who) {

	int res = 0;

	if (!B_NUM) return -INF;
	if (!W_NUM) return INF;
	if (B_NUM + W_NUM == N * N) return B_NUM > W_NUM ? INF : -INF;
	else if (dep == IMP_STEP && termin) return B_NUM - W_NUM;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (MAP[i][j] == 2) res += V[i][j];
			else if (MAP[i][j] == 1) res -= V[i][j];

	int c = 0;
	if (MAP[1][1] == 1) c--; else if (MAP[1][1] == 2) c++;
	if (MAP[1][N] == 1) c--; else if (MAP[1][N] == 2) c++;
	if (MAP[N][1] == 1) c--; else if (MAP[N][1] == 2) c++;
	if (MAP[N][N] == 1) c--; else if (MAP[N][N] == 2) c++;
	res += c * 6000000;
	int d1 = 0,d2 = 0,d3 = 0,d4 = 0,cross1 = 0,cross2 = 0;
	for (int i = 1; i <= N; i++)	
	{
		d1 += MAP[1][i] * e3[i - 1];
		d2 += MAP[i][1] * e3[i - 1];
		d3 += MAP[N][i] * e3[i - 1];
		d4 += MAP[i][N] * e3[i - 1];
		cross1 += MAP[i][i] * e3[i - 1];
		cross2 += MAP[i][N - i + 1] * e3[i - 1];
	}
	if (cross1 == 6560) res += 5000; else res -= 5000;
	if (cross2 == 6560) res += 5000; else res -= 5000;
	for (int i = 2; i < N; i++)
	{
		c = 0;
		for (int j = 1; j <= N; j++) c += MAP[i][j] * e3[i - 1];
		if (c == 6560) res += 700; else if (c == 3280) res -= 700;
	}	
	for (int j = 2; j < N; j++)
	{
		c = 0;
		for (int i = 1; i <= N; i++) c += MAP[i][j] * e3[i - 1];
		if (c == 6560) res += 700; else if (c == 3280) res -= 700;
	}	


	d1 = f[d1][who],d2 = f[d2][who],d3 = f[d3][who],d4 = f[d4][who];
	if (d1 == 2186 || d1 == 6558 || d1 == 1093 || d1 == 3279) d1 *= 400;
	else if (d1 == 6560 || d1 == 3280) d1 *= 1000;

	if (d2 == 2186 || d2 == 6558 || d2 == 1093 || d2 == 3279) d2 *= 400;
	else if (d2 == 6560 || d2 == 3280) d2 *= 1000;

	if (d3 == 2186 || d3 == 6558 || d3 == 1093 || d3 == 3279) d3 *= 400;
	else if (d3 == 6560 || d3 == 3280) d3 *= 1000;

	if (d4 == 2186 || d4 == 6558 || d4 == 1093 || d4 == 3279) d4 *= 400;
	else if (d4 == 6560 || d4 == 3280) d4 *= 1000;
	res += (d1 + d2 + d3 + d4) * 50000;
	return res;
}

int AI::Black_search(int P_MAP,int B_NUM,int W_NUM,int dep,int alpha,int beta,bool mark) { //machine drop black MAX


	POS_D PUTPOSS[257];
	int PUT_NUM,Rec[63][2];
	if (!W_NUM || dep==MAX_DEP) return Get_value(MAP,B_NUM,W_NUM,dep,0);

	Can_drop_black(MAP,PUTPOSS,NOW_BORDER,PUT_NUM);

	bool EXdir[8];
	int Dx,Dy,MAX=-INF;

	if (PUT_NUM)
	{
		for (int i=1; i<=PUT_NUM; i++)
		{
			memset(EXdir,0,sizeof(EXdir));
			Dx=PUTPOSS[i].x;
			Dy=PUTPOSS[i].y;

			Expand(Dx,Dy,NOW_BORDER,MAP,EXdir);
			Del(Dx,Dy,NOW_BORDER);
			int EAT_NUM=Drop_black(Dx,Dy,MAP,PUTPOSS[i].dir,Rec);//drop it!!!
			int S=White_search(MAP,B_NUM + EAT_NUM + 1,W_NUM - EAT_NUM,dep+1,alpha,beta,0); // calc
			Remove_black(Dx,Dy,MAP,Rec);
			for (int d=0; d<8; d++) if (EXdir[d]) Del(Dx+DET[d][0],Dy+DET[d][1],NOW_BORDER);
			Resume(Dx,Dy,NOW_BORDER);

			if (S>MAX) {MAX=S; if (dep == 1){Next_x = Dx; Next_y = Dy;}}
			if (MAX>=beta) return MAX;
			alpha=MAX;
		}
		return MAX;
	}
	else 
	{
		if (mark) return Get_value(MAP,B_NUM,W_NUM,dep,0);
		return White_search(MAP,B_NUM,W_NUM,dep,alpha,beta,1);
	}
}

int AI::White_search(int P_MAP,int B_NUM,int W_NUM,int dep,int alpha,int beta,bool mark) { //enemy drop white MIN


	POS_D PUTPOSS[257];
	int PUT_NUM,Rec[63][2];
	if (!B_NUM || dep==MAX_DEP) return Get_value(MAP,B_NUM,W_NUM,dep,1);

	Can_drop_white(MAP,PUTPOSS,NOW_BORDER,PUT_NUM);

	bool EXdir[8];
	int Dx,Dy,MIN=INF;

	if (PUT_NUM)
	{
		for (int i=1; i<=PUT_NUM; i++)
		{
			memset(EXdir,0,sizeof(EXdir));
			Dx=PUTPOSS[i].x;
			Dy=PUTPOSS[i].y;

			Expand(Dx,Dy,NOW_BORDER,MAP,EXdir);
			Del(Dx,Dy,NOW_BORDER);
			int EAT_NUM=Drop_white(Dx,Dy,MAP,PUTPOSS[i].dir,Rec);//drop it!!!
			int S=Black_search(MAP,B_NUM - EAT_NUM,W_NUM + EAT_NUM + 1,dep + 1,alpha,beta,0); // calc
			Remove_white(Dx,Dy,MAP,Rec);
			for (int d=0; d<8; d++) if (EXdir[d]) Del(Dx+DET[d][0],Dy+DET[d][1],NOW_BORDER);//
			Resume(Dx,Dy,NOW_BORDER);

			if (S<MIN) MIN=S;
			if (MIN<=alpha) return MIN;
			beta=MIN;
		}
		return MIN;
	}
	else
	{
		if (mark) Get_value(MAP,B_NUM,W_NUM,dep,0);
		return Black_search(MAP,B_NUM,W_NUM,dep,alpha,beta,1);
	}
}
///////////////////  MAP  Functions   /////////////////////

void MAP::Start(int P_MAP,POS* BORDER,int &PUT_NUM_BLACK,int &PUT_NUM_WHITE,int style) {
	memset(MAP,0,sizeof(MAP));
	PUT_NUM_WHITE=0;
	PUT_NUM_BLACK=0;

	int mid=N>>1;

	if (style == 1)
	{
		MAP[mid][mid]=1; MAP[mid][mid+1]=2;
		MAP[mid+1][mid]=2; MAP[mid+1][mid+1]=1;
	}
	else
	{
		MAP[mid][mid]=2; MAP[mid][mid+1]=1;
		MAP[mid+1][mid]=1; MAP[mid+1][mid+1]=2;
	}
	Expand(mid,mid,BORDER,MAP); Expand(mid,mid+1,BORDER,MAP);
	Expand(mid+1,mid,BORDER,MAP); Expand(mid+1,mid+1,BORDER,MAP);
	//center position
}

int MAP::Drop_black(int x,int y,int P_MAP,bool dir[6],int Rec[63][2]) {

	int c=0;

	MAP[x][y]=2; //drop it
	Rec[0][0] = 0;
	for (int d=0; d<8; d++)
		if (dir[d])
			for (int nx=x+DET[d][0],ny=y+DET[d][1]; MAP[nx][ny]==1 && 1<=nx && nx<=N && 1<=ny && ny<=N; nx+=DET[d][0],ny+=DET[d][1],c++)
			{
				MAP[nx][ny]=2; //reverse
				Rec[++Rec[0][0]][0] = nx;
				Rec[Rec[0][0]][1] = ny;
			}
	return c;
}

int MAP::Drop_white(int x,int y,int P_MAP,bool dir[6],int Rec[63][2]) {

	int c=0;

	MAP[x][y]=1; //drop it
	Rec[0][0] = 0;
	for (int d=0; d<8; d++)
		if (dir[d])
			for (int nx=x+DET[d][0],ny=y+DET[d][1]; MAP[nx][ny]==2 && 1<=nx && nx<=N && 1<=ny && ny<=N; nx+=DET[d][0],ny+=DET[d][1],c++)
			{
				MAP[nx][ny]=1; //reverse
				Rec[++Rec[0][0]][0] = nx;
				Rec[Rec[0][0]][1] = ny;
			}
	return c;
}

void MAP::Remove_black(int x,int y,int P_MAP,int Rec[63][2]) {

	MAP[x][y]=0; //remove it
	for (int i = 1; i <= Rec[0][0]; i++)
		MAP[Rec[i][0]][Rec[i][1]] = 1;
}

void MAP::Remove_white(int x,int y,int P_MAP,int Rec[63][2]) {

	MAP[x][y]=0; //remove it
	for (int i = 1; i <= Rec[0][0]; i++)
		MAP[Rec[i][0]][Rec[i][1]] = 2;
}

void MAP::Can_drop_black(int P_MAP,POS_D* PUT_POSS_BLACK,POS* BORDER,int &PUT_NUM_BLACK) {

	PUT_NUM_BLACK=0;
	memset(PUT_POSS_BLACK,0,sizeof(POS_D)*257);

	for (POS* now=BORDER->next; now!=NULL; now=now->next)
	{
		int tx=now->x,nx;
		int ty=now->y,ny;
		int c;
		bool exist=0;

		PUT_POSS_BLACK[++PUT_NUM_BLACK].x=tx;
		PUT_POSS_BLACK[PUT_NUM_BLACK].y=ty;

		for (int d=0; d<8; d++)
		{
			for (nx=tx+DET[d][0],ny=ty+DET[d][1],c=0; MAP[nx][ny]==1 && 1<=nx && nx<=N && 1<=ny && ny<=N; nx+=DET[d][0],ny+=DET[d][1],c++);
			if (MAP[nx][ny]==2 && c>0) {PUT_POSS_BLACK[PUT_NUM_BLACK].dir[d]=1; exist=1;}
		}

		if (!exist) PUT_NUM_BLACK--;//delete
	}
}

void MAP::Can_drop_white(int P_MAP,POS_D* PUT_POSS_WHITE,POS* BORDER,int &PUT_NUM_WHITE) {

	PUT_NUM_WHITE=0;
	memset(PUT_POSS_WHITE,0,sizeof(POS_D)*257);

	for (POS* now=BORDER->next; now!=NULL; now=now->next)
	{
		int tx=now->x,nx;
		int ty=now->y,ny;
		int c;
		bool exist=0;

		PUT_POSS_WHITE[++PUT_NUM_WHITE].x=tx;
		PUT_POSS_WHITE[PUT_NUM_WHITE].y=ty;

		for (int d=0; d<8; d++)
		{
			for (nx=tx+DET[d][0],ny=ty+DET[d][1],c=0; MAP[nx][ny]==2 && 1<=nx && nx<=N && 1<=ny && ny<=N; nx+=DET[d][0],ny+=DET[d][1],c++);
			if (MAP[nx][ny]==1 && c>0) {PUT_POSS_WHITE[PUT_NUM_WHITE].dir[d]=1; exist=1;}
		}

		if (!exist) PUT_NUM_WHITE--;//delete
	}
}

//----------about the list

POS* MAP::Find(int x,int y,POS* BORDER) {

	POS* pos=0x0;
	for (POS* now=BORDER->next; now!=NULL; now=now->next)
		if (now->x==x && now->y==y)
		{
			pos=now;
			break;
		}
	return pos;
}

void MAP::Expand(int x,int y,POS* BORDER,int P_MAP) {

	POS* tmp;

	for (int d=0; d<8; d++)
	{
		int nx=x+DET[d][0];
		int ny=y+DET[d][1];
		if (1<=nx && nx<=N && 1<=ny && ny<=N)
			if ((MAP[nx][ny]!=1 && MAP[nx][ny]!=2) && (Find(nx,ny,BORDER)==NULL))
			{
				tmp=new POS;
				tmp->x=nx;
				tmp->y=ny;
				tmp->next=BORDER->next; BORDER->next=tmp;
			}//insert
	}
}

void MAP::Expand(int x,int y,POS* BORDER,int P_MAP,bool* dir) {

	POS* tmp;

	for (int d=0; d<8; d++)
	{
		int nx=x+DET[d][0];
		int ny=y+DET[d][1];
		if (1<=nx && nx<=N && 1<=ny && ny<=N)
			if ((MAP[nx][ny]!=1 && MAP[nx][ny]!=2) && (Find(nx,ny,BORDER)==NULL))
			{
				tmp=new POS;
				tmp->x=nx;
				tmp->y=ny;
				tmp->next=BORDER->next; BORDER->next=tmp;
				dir[d]=1;
			}//insert
	}
}

void MAP::Del(int x,int y,POS* BORDER) {

	POS* tmp;
	for (POS* now=BORDER; now->next!=NULL; now=now->next)
		if (now->next->x==x && now->next->y==y)
		{
			tmp=now->next;
			now->next=now->next->next;
			delete tmp;
			break;
		}
}

void MAP::Resume(int x,int y,POS *BORDER) {

	POS*tmp;
	tmp = new POS;
	tmp -> x = x; tmp -> y = y;
	tmp ->next = BORDER -> next;
	BORDER -> next = tmp;
}

void MAP::view(POS* BORDER) {

	for (POS* now=BORDER->next; now!=NULL; now=now->next) 
		std::cout<<now->x<<' '<<now->y<<std::endl;
}

void MAP::Draw(int P_MAP,int x,int y) {

	printf("  ");
	for (int i=1; i<=N; i++) printf("%2d",i);
	printf("\n");
	for (int i=1; i<=N; i++)
	{
		printf("%2d ",i);
		for (int j=1; j<=N; j++)
		{
			switch (MAP[i][j])
			{
				case 0:printf("."); break;
				case 1:printf("o"); break;
				case 2:printf("x"); break;
			}
			if (i == x && j == y) printf("]");
			else if (!(i == x && j + 1 == y)) printf(" "); 
			else printf("[");

		}
		printf("\n");
	}
	printf("\n");
}

